import edu.princeton.cs.algs4.*;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class LinkedStack<Item> implements Iterable<Item>
{
    private int n;
    private Node first;

    private class Node
    {
       private Item item;
       private Node next;
    }

    public LinkedStack()
    {
        first = null;
        n = 0;
        assert check();
    }

    public boolean isEmpty()
    {
        return first == null;
    }
    
    public int size()
    {
        return n;
    }

    public void push(Item item)
    {
        Node oldFirst = first;

        first = new Node();
        first.item = item;
        first.next = oldFirst;
        n++;

        assert check();
    }

    public Item pop()
    {
        if(isEmpty())
            throw new NoSuchElementException("Stack Underflow");
        Item item = first.item;
        first = first.next;
        n--;

        assert check();

        return item;
    }

    public Item peek()
    {
        if(isEmpty())
            throw new NoSuchElementException("Stack Underflow");
        return first.item;
    }

    public String toString()
    {
        StringBuilder s = new StringBuilder();

        for(Item item : this)
            s.append(item + " ");

        return s.toString();
    }

    public Iterator<Item> iterator()
    {
        return new LinkedIterator();
    }

    private class LinkedIterator implements Iterator<Item> 
    {
        private Node current = first;

        public boolean hasNext()
        {
            return current != null;
        }

        public Item next()
        {
            if(!hasNext())
                throw new NoSuchElementException();

            Item item = current.item;
            current = current.next;
            return item;
        }
    }

    private boolean check()
    {
        if(n < 0)
        {
            return false;
        }

        if(n == 0)
        {
            if(first != null)
                return false;
        }
        else if(n == 1)
        {
            if(first == null)
                return false;
            if(first.next != null)
                return false;
        }
        else 
        {
            if(first == null)
                return false;
            if(first.next == null)
                return false;
        }

        int nOfNodes = 0;
        for(Node x = first; x != null && nOfNodes <= n; x = x.next)
        {
            nOfNodes++;
        }

        if(nOfNodes != n)
            return false;

        return true;
    }

    public static void main(String[] args)
    {
        LinkedStack<String> stack = new LinkedStack<String> ();

        int m = 10;

        while(m-- > 0)
        {
            String item = StdIn.readString();

            if(!item.equals("-"))
                stack.push(item);
            else if(!stack.isEmpty())
                StdOut.print(stack.pop() + " ");
        }

        StdOut.println("(" + stack.size() + " left on stack)");
        StdOut.println(stack);
    }

}
